package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;

/**
 * <a href="https://leetcode.cn/problems/maximum-subarray/">53. 最大子数组和</a>
 */
public class LeetCode53 {

    public int maxSubArray(int[] nums) {
        final int[] m = new int[nums.length];
        m[0] = nums[0];
        int maxSub = m[0];
        for (int i = 1; i < nums.length; i++) {
            m[i] = Math.max(m[i - 1] + nums[i], nums[i]);
            maxSub = Math.max(maxSub, m[i]);
        }
        return maxSub;
    }

    public static void main(String[] args) {
        final LeetCode53 demo = new LeetCode53();
        {
            Assertions.assertEquals(6,
                    demo.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        }
        {
            Assertions.assertEquals(1,
                    demo.maxSubArray(new int[]{1}));
        }
        {
            Assertions.assertEquals(23,
                    demo.maxSubArray(new int[]{5, 4, -1, 7, 8}));
        }
    }
}
